import { useState, useMemo } from 'react';
import { lowestCommonAncestor, TreeNode } from '@ds/tree';
import { Space, Input, Select, Typography, Alert, Card } from 'antd';
import type { SelectProps } from 'antd';

const { Title } = Typography;

/**
 * 查找树中特定值的节点
 */
function findNode(root: TreeNode | null, val: number): TreeNode | null {
  if (!root) return null;
  if (root.val === val) return root;
  return findNode(root.left, val) || findNode(root.right, val);
}

/**
 * 生成树的层级遍历表示
 */
function levelOrder(root: TreeNode | null): (number | null)[][] {
  const result: (number | null)[][] = [];
  if (!root) return result;
  const queue: (TreeNode | null)[] = [root];
  while (queue.length) {
    const size = queue.length;
    const level: (number | null)[] = [];
    for (let i = 0; i < size; i++) {
      const node = queue.shift() ?? null;
      if (node) {
        level.push(node.val);
        queue.push(node.left);
        queue.push(node.right);
      } else {
        level.push(null);
      }
    }
    // 避免尾部全是null的层级
    if (level.some((v) => v !== null)) {
      result.push(level);
    }
  }
  return result;
}

export default function BinaryTreeLCA() {
  const [input, setInput] = useState('3,5,1,6,2,0,8,null,null,7,4');
  const [pValue, setPValue] = useState<number | null>(null);
  const [qValue, setQValue] = useState<number | null>(null);

  // 解析输入数组
  const values = useMemo(
    () =>
      input
        .split(/[\,\s]+/)
        .filter(Boolean)
        .map((v) => (v === 'null' ? null : Number(v)))
        .filter((n) => n === null || Number.isFinite(n)),
    [input]
  );

  // 构建二叉树（这里我们仍然使用buildBSTFromArray，但实际上LCA适用于任何二叉树）
  const root = useMemo(() => {
    if (!values.length || values[0] === null) return null;

    // 对于LCA问题，我们构建一个普通二叉树而不是BST
    // 使用层序遍历方式构建树
    const root = new TreeNode(values[0]);
    const queue: TreeNode[] = [root];
    let i = 1;

    while (queue.length > 0 && i < values.length) {
      const current = queue.shift();
      if (!current) continue;

      // 左子节点
      if (i < values.length && values[i] !== null) {
        current.left = new TreeNode(values[i] as number);
        queue.push(current.left);
      }
      i++;

      // 右子节点
      if (i < values.length && values[i] !== null) {
        current.right = new TreeNode(values[i] as number);
        queue.push(current.right);
      }
      i++;
    }

    return root;
  }, [values]);

  // 获取树中所有非null节点的值作为选择选项
  const nodeValues = useMemo(() => {
    const uniqueValues = new Set<number>();

    function collectValues(node: TreeNode | null) {
      if (!node) return;
      uniqueValues.add(node.val);
      collectValues(node.left);
      collectValues(node.right);
    }

    collectValues(root);
    return Array.from(uniqueValues).sort((a, b) => a - b);
  }, [root]);

  // 查找最近公共祖先
  const lca = useMemo(() => {
    if (!root || pValue === null || qValue === null) return null;

    const pNode = findNode(root, pValue as number);
    const qNode = findNode(root, qValue as number);

    if (!pNode || !qNode) return null;

    return lowestCommonAncestor(root, pNode, qNode);
  }, [root, pValue, qValue]);

  // 节点选项配置
  const nodeOptions: SelectProps<number>['options'] = nodeValues.map((val) => ({
    value: val,
    label: val.toString(),
  }));

  // 生成树的可视化结构
  const treeLevels = useMemo(() => levelOrder(root), [root]);

  return (
    <Space direction="vertical" size="middle" style={{ width: '100%' }}>
      <Title level={2}>LeetCode 236. 二叉树的最近公共祖先</Title>

      <Alert
        message="题目说明"
        description={
          <Typography.Paragraph style={{ marginBottom: 0 }}>
            给定一个二叉树，找到该树中两个指定节点的最近公共祖先（LCA）。
            <br />
            最近公共祖先是指：对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是
            p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
            <Typography.Link
              href="https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/"
              target="_blank"
              style={{ marginLeft: 8 }}
            >
              题目链接
            </Typography.Link>
          </Typography.Paragraph>
        }
        type="info"
        showIcon
      />

      <Space>
        <Input
          allowClear
          value={input}
          onChange={(e) => setInput(e.target.value)}
          placeholder="例如: 3,5,1,6,2,0,8,null,null,7,4"
          style={{ width: 400 }}
        />
      </Space>

      <Space>
        <span>选择节点 p: </span>
        <Select
          allowClear
          style={{ width: 120 }}
          value={pValue}
          onChange={(value) => setPValue(value)}
          options={nodeOptions}
          placeholder="选择节点"
        />
        <span>选择节点 q: </span>
        <Select
          allowClear
          style={{ width: 120 }}
          value={qValue}
          onChange={(value) => setQValue(value)}
          options={nodeOptions}
          placeholder="选择节点"
        />
      </Space>

      {pValue !== null && qValue !== null && (
        <Alert
          message={`最近公共祖先: ${lca ? lca.val : '未找到有效节点'}`}
          type={lca ? 'success' : 'warning'}
          showIcon
        />
      )}

      <Card title="二叉树可视化" style={{ width: '100%', minHeight: 300 }}>
        {treeLevels.length > 0 ? (
          <div style={{ display: 'flex', justifyContent: 'center' }}>
            <div>
              {treeLevels.map((level, levelIndex) => (
                <div
                  key={levelIndex}
                  style={{
                    display: 'flex',
                    justifyContent: 'center',
                    marginBottom: 20,
                  }}
                >
                  {level.map((val, index) => {
                    const isLCA = lca && val === lca?.val;
                    const isP = val === pValue;
                    const isQ = val === qValue;

                    let backgroundColor = '#fff';
                    if (isLCA) backgroundColor = '#ffe58f';
                    if (isP || isQ) backgroundColor = '#b7eb8f';
                    if ((isP || isQ) && isLCA) backgroundColor = '#fadb14';

                    return val !== null ? (
                      <div
                        key={index}
                        style={{
                          minWidth: 36,
                          minHeight: 36,
                          border: '1px solid #aaa',
                          borderRadius: 18,
                          display: 'flex',
                          alignItems: 'center',
                          justifyContent: 'center',
                          margin: '0 5px',
                          background: backgroundColor,
                        }}
                        title={(isLCA ? 'LCA ' : '') + (isP ? '节点p ' : '') + (isQ ? '节点q' : '')}
                      >
                        {val}
                      </div>
                    ) : (
                      <div
                        key={index}
                        style={{
                          minWidth: 36,
                          minHeight: 36,
                          margin: '0 5px',
                        }}
                      >
                        <span style={{ color: '#ccc' }}>null</span>
                      </div>
                    );
                  })}
                </div>
              ))}
            </div>
          </div>
        ) : (
          <Typography.Text type="secondary" style={{ textAlign: 'center', display: 'block' }}>
            请输入有效的树节点数据
          </Typography.Text>
        )}
      </Card>

      <Typography.Text type="secondary">
        注：输入格式为层序遍历的节点值，null表示空节点。选中的节点p和q会以绿色高亮显示，最近公共祖先以黄色高亮显示，既是LCA又是p或q的节点以亮黄色显示。
      </Typography.Text>
    </Space>
  );
}
